Лексикографический порядок

Лексикографический порядок — отношение линейного порядка на множестве слов над некоторым упорядоченным алфавитом $\Sigma$. Своё название лексикографический порядок получил по аналогии с сортировкой по алфавиту в словаре.

Определение

Слово $\alpha$ предшествует слову $\beta$ ($\alpha$ ≺ $\beta$), если

• либо первые $m$ символов этих слов совпадают, а $m+1$-й символ слова $\alpha$ меньше (относительно заданного в $\Sigma$ порядка) $m+1$-го символа слова $\beta$ (например, АБАК ≺ АБРАКАДАБРА, так как первые две буквы у этих слов совпадают, а третья буква у первого слова меньше, чем у второго);
• либо слово $\alpha$ является началом слова $\beta$ (например, МАТЕМАТИК ≺ МАТЕМАТИКА; см. конкатенация).

Примеры

• Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Например, следующие слова идут в лексикографическом порядке: А ≺ АА ≺ ААА ≺ ААБ ≺ ААВ ≺ АБ ≺ АВ ≺ Б ≺ … ≺ ЯЯЯ.
• Естественный порядок на неотрицательных целых $n$-значных числах в любой позиционной системе счисления, записанных в разрядной сетке фиксированной длины (000, 001, 002, 003, 004, 005, …, 998, 999).